This invention relates generally to image processing and, more particularly, relates to an image processing technique for eliminating ripples that occur within images that are resized.
Image filtering and reconstruction are computational processes used commonly within computer software applications to affect how digital images, picture files and other graphic elements are rendered to a computer display device, such as a monitor. Typically, these image-processing techniques are used for resizing, repositioning and/or rotating an image, which in effect is a modification of the pixel data comprising the image. Pixels, short for picture elements, are the smallest addressable units that appear on a display screen. Multiple pixels, or samples, of varying color intensities are combined to represent a given image. The higher the pixel resolution (the more rows and columns of pixels), the more information can be displayed to the screen. Image filtering is a process by which a new image is generated as a result of processing the pixels of an existing image.
As an example of image filtering applied within software, consider the commonly used word processing application Microsoft Word. A useful feature of Word is that it allows a user to insert digitally sampled images, such as those scanned into the computer using a scanner, directly into a text document. This is particularly useful for creating newsletters, reports, and other published works that require high graphic content. Whenever the user wants to alter the natural size of an image embedded within the document (e.g. shrink it), they need only adjust it manually by toggling it with the mouse or by selecting the appropriate user commands. In resizing the image from its natural size or scale (100%) to a smaller size (x %; x less than 100), an image-filtering algorithm is applied to the source image pixel data to yield the appropriately resized output image. In computer graphics terms, shrinking an image is the process of representing the signal (waveform) representative of the source image with a similarly shaped output signal (waveform) of reduced size.
According to conventional techniques, a scaled down version of the original (sampled) image is generated using convolution filtering. Convolution filtering is an operation wherein the intensity value of a pixel to be placed into the output image is determined by summing up the intensity contributions of a group of pixels in the neighborhood of a source pixel. A neighborhood is defined as a range of pixels surrounding the source pixel. The number of pixels within the range is determined by the width of a filter kernel. Simply defined, the filter kernel is an array of values (weights) that characterize the type of filtering operation to be performed on the source image.
Filter kernels are not restricted to any particular size, and can be of varying shapes, including box shaped, tent shaped (bilinear) or an approximation to the sinc function (e.g., bi-cubic). Regardless of the shape, the filter kernel is typically symmetric about a two dimensional axis, and is designed so that the area, or response of the filter with respect to varying scale factors (x) is always unity. This is achieved by resizing the kernel width by the scale factor (x), while the height is resized to be the reciprocal of the scale factor (1/x). Unity response is maintained so that as the filter is applied to the source image, it is filtered as a constant value function, and not a periodic one. From a mathematical standpoint, this corresponds to filtering the waveform representative of the source image at a constant rate (constant number of pixels) to ensure the intensity contribution for each pixel is accounted for to represent the resized image. A non-unity filter kernel response can lead to pixel contributions that are not accounted for during the filtering process, thus creating unwanted visual effects in the output image.
In general, the filtering process begins by centering the filter kernel at a row/column position within the source image that corresponds to the location of the desired output pixel. Based on the width of the kernel, a number of pixels will lie beneath the kernel as it is centered accordingly. The resulting output pixel is calculated by multiplying the pixel values with the weight of the filter kernel at each respective row/column position of the pixels underneath the kernel. These values are then summed to reveal the total output pixel value, and placed into the output image. This process is repeated by shifting the filter, pixel by pixel, until each source pixel within the source image has been processed. The typical filtering process described above results in a desirable output image being generated. Because of the inverse relationship between the filter kernel width and height as set according to the selected rescale factor (x); a unity filter response is often maintained. As long as the number of pixels underneath the kernel remains constant throughout the filtering processxe2x80x94as the filter is shifted from pixel to pixel, the contribution for each pixel is accounted for in calculating the output pixel value. However, when a rescale factor (x) is selected that results in the filter kernel being resized to a non-integer width and height, unity area under the kernel is not maintained. This results in highly objectionable visual artifacts, such as ripples, being displayed in the output image. Ripples appear within digital images as longitudinal gaps of obscure color. They are visible within each of the color channelsxe2x80x94red, blue, green and a (transparent)xe2x80x94that comprise a color image. Ripples occur whenever the filter kernel is set to a non-integer width as a result of resealing the image by the designated value x. For instance, if the rescale factor (x) is selected as 2.5, the filter width and height is adjusted from its default setting to 2.5 and 1/2.5 respectively. Because of this non-integer setting, the number of pixels that lie underneath the kernel as it is moved from pixel to pixel changes as opposed to remaining constant. This results in a cyclical pattern of increasing and decreasing filter kernel response that manifests as patterns of light and dark lines in the resized image. Clearly, this is not acceptable visual quality, particularly for those applications requiring rich graphic content.
Fortunately, there are some standard processes available for eliminating the ripple effect that occurs within images. For instance, one such method is to increase the size of the filter kernel such that significantly more pixels lie under the kernel as it is moved across the source image. This reduces the possibility of a non-constant filter response, and provides a more accurate approximation of the output pixel value. Also, there are other processes such as edge reduction and stochastic filtering, which also reduce unwanted visual peculiarities within digitally sampled images. However, these techniques are not always practical because they require a considerable amount of random-access memory (RAM) to operate on source image representations. This impedes the performance of software applications, such as word-processing or publishing software, that demand quick image processing capability. Moreover, the resource usage required to perform these techniques increases the software development and test process, negatively impacting the cost to the developer and consumer. To overcome these challenges, a way is needed to provide ripple free image rendering techniques that require only modest processing and memory resources.
The present invention is directed to a method and system for resizing an image to produce an output image that is free of ripples. Particularly, the invention eliminates the ripple effect that occurs within graphic images as a result of resizing, rescaling, or reconstruction without reliance upon high cost, impractical processing methods.
In accordance with the invention, an optimal filter kernel is formed by convolving a box filter with a filter of fixed integer width and unity area. The filter of fixed integer width and unity area can be any standard filter that is symmetric about an axis, including bilinear or bicubic. The resultant optimal filter has forced zeros at locations along a frequency scale corresponding to the reciprocal of the spacing of one or more pixels that comprise a source image to be resized. In the spatial domain, this corresponds to a filter having characteristics such that a constant filter response is maintained as the filter is moved from pixel to pixel within the source image. Upon the selection of a rescale value for the source image, the optimal filter kernel is computed and then mapped to the source image. Specifically, the filter is mapped and centered upon a location within the source image corresponding to the position of an output pixel to be generated. The number of pixels that lie underneath the optimal filter is established by multiplying the number of pixels that comprise the width of the source image by the selected rescale value. Upon mapping the optimal filter, the output pixel values that comprise the resized image are then evaluated by processing the one or more pixels that comprise the source image, such as through interpolation. These values are then placed into a memory/buffer allocated for the output image, resulting in an output image generated free of ripples.
In another aspect of the invention, partial integral analysis is applied with respect to a standard filter kernel of fixed integer width and unity area (e.g., bilinear or bicubic). The number of pixels that lie underneath the filter once it is mapped to the source image is established by multiplying the number of pixels that comprise the width of the source image by the selected rescale value. Upon mapping the filter, the output pixel values of the resized image are calculated by multiplying the pixel value for each pixel under the kernel by the area of the filter kernel surrounding the pixel. The products are then summed to reveal the output pixel value, and placed into the output image buffer. This operation is performed repeatedly on each pixel of the source image until the resized output image is fully generated. Because the computation of the output pixel is performed using partial integral analysis, a lookup table containing the total area of the filter kernel (instead of actual kernel values for specific points) can be implemented. This speeds up the computation process, while still producing a ripple free output image.
Additional features and advantages of the invention will be made apparent from the following detailed description of illustrative embodiments that proceeds with reference to the accompanying figures.